public class Solution235 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val>q.val){
            TreeNode t=q;
            q=p;
            p=t;
        }
        while (!(root.val>=p.val && root.val<=q.val)){
            if (q.val<root.val){
                root=root.left;
            }else{
                root=root.right;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode t0=new TreeNode(0);
        TreeNode t3=new TreeNode(3);
        TreeNode t5=new TreeNode(5);
        TreeNode t4=new TreeNode(4,t3,t5);
        TreeNode t2=new TreeNode(2,t0,t4);
        TreeNode t7=new TreeNode(7);
        TreeNode t9=new TreeNode(9);
        TreeNode t8=new TreeNode(8,t7,t9);
        TreeNode t6=new TreeNode(6,t2,t8);
        System.out.println(new Solution235().lowestCommonAncestor(t6,t2,t4).val);
    }
}
